package hh.leecode;

import java.util.*;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * 示例 4:
 * <p>
 * 输入: s = ""
 * 输出: 0
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class a3无重复字符的最长子串 {


    public static void main(String[] args) {
        a3无重复字符的最长子串 obj = new a3无重复字符的最长子串();
        //        obj.lengthOfLongestSubstring4("abcabcbb");
        //        obj.lengthOfLongestSubstring4("bbbbb");
        //        obj.lengthOfLongestSubstring4("pwwkew");
        //        obj.lengthOfLongestSubstring4("");
        obj.asdfaf("bpfbhmipx");
        obj.intHashMap("bpfbhmipx");
        obj.intHashMap("abcabcbb");
        obj.intHashMap("pwwkew");
        obj.intHashMap("");
    }

    //  用hashMap方法
    public int hasmMap(String s) {
        int len = s.length();
        Map<Character, Integer> window = new HashMap<>(100);
        int max = 0;
        int windowStart = 0;
        Character c;
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            Integer idx = window.get(c);
            if (idx != null) {
                for (; windowStart <= idx; windowStart++) {
                    window.remove(s.charAt(windowStart));
                }
            }
            window.put(c, i);
            if (max < window.size())
                max = window.size();
        }
        System.out.println(max);
        return max;
    }

    //  string中的每个char就是一个int值，所以可以将他的int值当做hashcode 存到数组，就变成一个hashmap了
    public int intHashMap(String s) {
        // 记录字符上一次出现的位置
        int[] hashMap = new int[128];
        for (int i = 0; i < 128; i++) {
            hashMap[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for (int i = 0; i < n; i++) {
            // 相当于得到char的 int值，把这个值当做数组下标，value存数组索引
            int index = s.charAt(i);
            // start是滑动窗口左边界
            start = Math.max(start, hashMap[index] + 1);
            // res是max len, 要么是上次的,要么是这次-start
            res = Math.max(res, i - start + 1);
            hashMap[index] = i;
        }

        return res;
    }

    public int hashSet(String s) {
        int len = s.length();
        Set<Character> window = new HashSet<>(100);
        int windowStart = 0;
        int max = 0;
        Character c;
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            while (window.contains(c)) {
                window.remove(s.charAt(windowStart++));
            }
            window.add(c);
            if (max < window.size())
                max = window.size();
        }
        return max;
    }

    public int asdfaf(String s) {
        int hashmap[] = new int[130];
        char[] s1 = s.toCharArray();
        int max = 0;
        int n = s.length();
        for (int i = 0, j = 0; j < n; j++) {//当前判断是否重复的串为s[i..j]
            hashmap[s1[j]]++;
            while (hashmap[s1[j]] > 1) { // 相当于map.containsKey  remove
                hashmap[s1[i++]]--;  // 不可取，相当于遍历
//                i++;
            }
            if (j - i + 1 > max)
                max = j - i + 1;
        }
        System.out.println(max);
        return max;
    }



    // stringbuilder 方法
    public int stringbuilder(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        StringBuilder current = new StringBuilder(s.length() / 2);
        StringBuilder max = new StringBuilder(s.length() / 2);
        int lastStart = 0;


        for (int i = 0; i < length; i++) {
            char c = chars[i];
            int index = index(current, c);
            if (index != -1) {
                int startIdx = index + lastStart + 1;
                if (max.length() < current.length()) {
                    max = current;
                }
                current.setLength(0);
                current.append(chars, startIdx, i - startIdx + 1);
                lastStart = startIdx;

            } else {
                current.append(c);
            }
        }
        if (max.length() < current.length()) {
            max = current;
        }
        System.out.println(max);
        return max.length();
    }

    private int index(StringBuilder current, char c) {
        int len = current.length();
        for (int i = 0; i < len; i++) {
            if (current.charAt(i) == c)
                return i;
        }
        return -1;
    }
}





